package leetcode.search;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。

 candidates中的每个数字在每个组合中只能使用一次。

 注意：解集不能包含重复的组合。'
 candidates = [10,1,2,7,6,1,5], target = 8,
 [
 [1,1,6],
 [1,2,5],
 [1,7],
 [2,6]
 ]
 */
public class CombinationSum39 {

    public static void main(String[] args) {
        int []  candidates = new int[]{2,3,6,7};
        List<List<Integer>> res = new CombinationSum39().combinationSum2(candidates, 7);
        for (List<Integer> re : res) {
            System.out.println(re);
        }



    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> tempList = new LinkedList<>();

//        combinationSum2(candidates,res,tempList,0,0, target);
        combinationSum3(candidates,res,tempList,0,0,target);
        return  res;
    }

    public void combinationSum2(int[] candidates, List<List<Integer>> res, LinkedList<Integer> temList, int index, int cur, int target) {
        if(index== candidates.length){
            return ;
        }

        if(cur==target){
            ArrayList<Integer> temp = new ArrayList<>(temList);
            res.add(temp);
            return;
        }


        combinationSum2(candidates,res,temList,index+1,cur,target);//不考虑这个数

        if(cur+candidates[index]<=target){//考虑这个数
            temList.offer(candidates[index]);
            combinationSum2(candidates,res,temList,index,cur+candidates[index],target);
            temList.removeLast();//回溯还原状态
        }
    }

    public void combinationSum3(int[] candidates, List<List<Integer>> res, LinkedList<Integer> temList, int index,int cur, int target) {
        if(cur > target){
            return ;
        }

        if(cur==target){
            ArrayList<Integer> temp = new ArrayList<>(temList);
            res.add(temp);
            return;
        }


        for (int i = index; i < candidates.length; i++) {
            temList.offer(candidates[i]);
            combinationSum3(candidates,res,temList,i,cur+candidates[i],target);
            temList.removeLast();//回溯还原状态
        }
    }
}